#include <iostream>

using namespace std;

/*
数组：一种连续的数据结构 - 数组的元素是一个挨着一个存储的
[1, 2, 3, 4, 5]
[1, 6, 2, 3, 4, 5]
vector 的不足，在 vector 中间插入元素的时候效率不好

链表：非连续存储的结构
1->2->3->4->5
*/

// 链表中的节点
class Node {
public:
  // 节点保存的值
  int value;

  // 节点的下一个节点的位置
  // Node *: 指向 Node 的指针。保存一个 Node 变量位置的变量
  Node *next;

  // 构造函数
  Node(int v) {
    value = v;
    next = nullptr; // nullptr 空指针
  }
};

class LinkedList {
public:
  // 如果链表只能有一个属性，你们认为应该是什么呢？
  // 表头
  Node *head;

  // 构造函数
  LinkedList() {
    head = nullptr;
  }
// private:
  void push_back(int n) {
    // 准备工作：用 n 创建一个 Node
    Node tmp(n);
    //
    // 情况1. 如果是一个空链表，就让 head 指向 Node
    //
    if (head == nullptr) {
      head = &tmp; // TO BE FIXED
    }
    // 情况2. 如果不是空链表，从 head 开始遍历到表尾，让老的表尾.next 指向 Node
    //
    else {
      Node *pN = head;

      while (pN->next != nullptr) {
        pN = pN->next;
      }

      pN->next = &tmp; // TO BE FIXED
    }
  }

  void print_list() {
    if (head == nullptr) {
      cout << "An empty linked list." << endl;
    }
    else {
      Node *pN = head;

      while (pN != nullptr) {
        cout << pN->value << " ";
        pN = pN->next;
      }

      cout << endl;
    }
  }
};
